//
// Created by TNJ on 2021/6/15.
//
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "binary_tree.h"

binary_tree_node_t *new_binary_tree_node(data_type_t data){
    binary_tree_node_t *tree_node = (binary_tree_node_t *)malloc(sizeof(binary_tree_node_t));
    if(!tree_node){
        return NULL;
    }
    tree_node->data = data;
    tree_node->left = NULL;
    tree_node->right = NULL;

    return tree_node;
}

void free_binary_tree_node(binary_tree_node_t *node){
    if(node == NULL){
        return;
    }
    node->right = NULL;
    node->left = NULL;
    free(node);
    node = NULL;
}

void binary_tree_insert(binary_tree_node_t **root, data_type_t data){
    if(root == NULL){
        return;
    }
    if(*root == NULL){
        return;
    }
    binary_tree_node_t *tree_node = new_binary_tree_node(data);
    if(tree_node == NULL){
        return;
    }
    binary_tree_node_t *tree_root = *root;

    while(tree_root != NULL){
        if(data < tree_root->data){
            if(tree_root->left == NULL){
                break;
            }
            tree_root = tree_root->left;
        }else{
            if(tree_root->right == NULL){
                break;
            }
            tree_root = tree_root->right;
        }
    }
    if(data < tree_root->data){
        tree_root->left = tree_node;
    }else{
        tree_root->right = tree_node;
    }
}

binary_tree_node_t *binary_tree_find(binary_tree_node_t *root, data_type_t data){
    if(root == NULL){
        return NULL;
    }

    while(root != NULL){
        if(root->data == data){
            break;
        }else if(data < root->data){
            root = root->left;
        }else{
            root = root->right;
        }
    }

    return root;
}

//向左旋转
static void left_rotate(binary_tree_node_t **node, binary_tree_node_t *tree_root){
    if(node == NULL || tree_root == NULL){
        return;
    }
    if(*node == NULL){
        return;
    }
    binary_tree_node_t *temp_node = NULL;
    binary_tree_node_t *left = NULL;

    *node = tree_root->right;  //目标结点的右子结点代替目标结点
    temp_node = tree_root->left;  //保存目标右子结点的左子结点
    left = tree_root->right->left;
    //遍历目标结点的左子结点的最右结点
    while(left != NULL && left->left != NULL){
        left = left->left;
    }
    if(left != NULL){
        //目标结点的左子结点的最右结点指向原目标结点右结点的左子结点
        left->left = temp_node;
    }
    tree_root->left = NULL;
    tree_root->right = NULL;
}

//向右旋转
static void right_rotate(binary_tree_node_t **node, binary_tree_node_t *tree_root){
    if(node == NULL || tree_root == NULL){
        return;
    }
    if((*node) == NULL){
        return;
    }
    binary_tree_node_t *temp_node = NULL;
    binary_tree_node_t *right = NULL;

    *node = tree_root->left;    //目标结点的左子结点代替目标结点
    temp_node = tree_root->right;  //保存目标结点左子结点的右子结点
    right = tree_root->right;
    //遍历查找目标结点右子结点的最左结点
    while(right != NULL && right->right != NULL){
        right = right->right;
    }
    if(right != NULL){
        //目标结点的右子结点的最左结点指向将原目标结点左子结点的右子结点
        right->right = temp_node;
    }
    tree_root->left = NULL;
    tree_root->right = NULL;
}

void binary_tree_delete(binary_tree_node_t **root, data_type_t data){
    if(root == NULL){
        return;
    }
    if(*root == NULL){
        return;
    }

    binary_tree_node_t *tree_root = *root;
    binary_tree_node_t *left = NULL;
    binary_tree_node_t *right = NULL;
    binary_tree_node_t *parent = NULL;
    binary_tree_node_t *temp_node = NULL;
    srand(time(NULL));
    int rand_value = 0;

    while(tree_root != NULL){
        if(tree_root->data == data){
            break;
        }else if(data < tree_root->data){
            parent = tree_root;
            tree_root = tree_root->left;
        }else{
            parent = tree_root;
            tree_root = tree_root->right;
        }
    }
    //没有在树中找到结点
    if(tree_root == NULL){
        return;
    }
    if(*root == tree_root){
        //根结点被删除
        if(tree_root->right){
            //右节点不为空
            left = tree_root->right->left;
            tree_root->right->left = tree_root->left;
            *root = tree_root->right;
            if(left != NULL){
                temp_node = left->left;
                while(temp_node != NULL && temp_node->left){
                    temp_node = temp_node->left;
                }
                if(temp_node != NULL){
                    temp_node->left = tree_root->left;
                }
            }
            free_binary_tree_node(tree_root);
            return;
        }else if(tree_root->left){
            //左结点不为空
            *root = tree_root->left;
            free_binary_tree_node(tree_root);
            return;
        }else{
            //左节点和右结点都为空
            free_binary_tree_node(tree_root);
            *root = NULL;
            return;
        }
    }else{
        //判断结点是否是子结点，如果是子结点则直接释放内存
        if(tree_root->left == NULL && tree_root->right == NULL){
            if(parent->left == tree_root){
                parent->left = NULL;
            }else{
                parent->right = NULL;
            }
            free_binary_tree_node(tree_root);
            return;
        }
        //该结点是非子结点
        //产生随机数0-1，目的使得二叉树不至于成为一个链表
        // 0则用目标结点的右子结点代替原目标结点，1则用目标结点的左子结点代替原目标结点
        rand_value = rand() % 2;

        if(parent->left == tree_root){
            //目标结点是左子结点
            if(rand_value){
                //若目标结点的左子结点为空，则用右子结点代替原来的结点
                if(tree_root->left == NULL){
                    parent->left = tree_root->right;
                    free_binary_tree_node(tree_root);  //释放目标结点内存
                    return;
                }
                right_rotate(&(parent->left), tree_root);  //向右旋转
                free_binary_tree_node(tree_root);
            }else{
                //目标结点的右子结点为空，则用左子结点代替原来的结点
                if(tree_root->right == NULL){
                    parent->left = tree_root->left;
                    free_binary_tree_node(tree_root);  //释放目标结点内存
                    return;
                }
                left_rotate(&(parent->left), tree_root);  //向左旋转
                free_binary_tree_node(tree_root);
            }
        }else{
            //目标结点是右子结点
            if(rand_value){
                //若目标结点的左子结点为空，则用右子结点代替原来的结点
                if(tree_root->left == NULL){
                    parent->right = tree_root->right;
                    free_binary_tree_node(tree_root);  //释放目标结点内存
                    return;
                }
                right_rotate(&(parent->right), tree_root);  //向右旋转
                free_binary_tree_node(tree_root);
            }else{
                //目标结点的右子结点为空，则用左子结点代替原来的结点
                if(tree_root->right == NULL){
                    parent->right = tree_root->left;
                    free_binary_tree_node(tree_root);  //释放目标结点内存
                    return;
                }
                left_rotate(&(parent->right), tree_root);  //向左旋转
                free_binary_tree_node(tree_root);
            }
        }
    }
}

//只能后序遍历销毁二叉树
void binary_tree_destroy(binary_tree_node_t *root){
    if(root == NULL){
        return;
    }
    binary_tree_destroy(root->left);
    binary_tree_destroy(root->right);
    free_binary_tree_node(root);
}

//后序遍历
void binary_tree_print(binary_tree_node_t *root){
    if(root == NULL){
        return;
    }
    binary_tree_print(root->left);
    binary_tree_print(root->right);
    printf("%d ", root->data);
}

void preorder_traversal_binary_tree(binary_tree_node_t *root){
    if(root == NULL){
        return;
    }
    printf("%d ", root->data);
    preorder_traversal_binary_tree(root->left);
    preorder_traversal_binary_tree(root->right);
}

void middle_order_traversal_binary_tree(binary_tree_node_t *root){
    if(root == NULL){
        return;
    }
    preorder_traversal_binary_tree(root->left);
    printf("%d ", root->data);
    preorder_traversal_binary_tree(root->right);
}

void postorder_traversal_binary_tree(binary_tree_node_t *root){
    if(root == NULL){
        return;
    }
    preorder_traversal_binary_tree(root->left);
    preorder_traversal_binary_tree(root->right);
    printf("%d ", root->data);
}